package algorithm;

/**
 * 19. 删除链表的倒数第N个节点
 */
public class T00019 {
    public static void main(String[] args) {
        ListNode head = build(1,2);
//        print(head);
        print(new Solution().removeNthFromEnd(head, 2));
    }

    static void print(ListNode head) {
        if(head == null)
            return;
        ListNode c = head;
        while(true) {
            System.out.print(c.val);
            if((c = c.next) == null)
                break;
            System.out.print(" -> ");
        }
        System.out.println();
    }

    static ListNode build(int... arr) {
        ListNode head = null;
        for (int i = arr.length - 1; i >= 0; i --) {
            ListNode t = new ListNode(arr[i]);
            t.next = head;
            head = t;
        }
        return head;
    }

static class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode sentinel = new ListNode(-1);
        sentinel.next = head;
        ListNode p = findLastN(sentinel, n + 1);
        p.next = p.next.next;
        return sentinel.next;
    }

    public ListNode findLastN(ListNode head, int n) {
        ListNode p1 = head, p2 = head;
        while (n -- > 0) {
            p2 = p2.next;
        }
        while (p2 != null) {
            p2 = p2.next;
            p1 = p1.next;
        }
        return p1;
    }
}

    static class ListNode {
        int val;
        ListNode next;
        ListNode(int x) { val = x; }
    }
}